// 双向链表
class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
    this.prev = null;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  append(element) {
    let newNode = new Node(element);
    // 判断列表是否为空
    if (this.head == null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.size++;
  }
  forwardString() {
    let current = this.head;
    let forwardStr = "";
    while (current) {
      forwardStr += "," + current.element;
      current = current.next;
    }
    return forwardStr.slice(1);
  }
  reverseString() {
    let current = this.tail;
    let reverseStr = "";
    while (current) {
      reverseStr += "," + current.element;
      current = current.prev;
    }
    return reverseStr.slice(1);
  }
  toString() {
    return this.forwardString();
  }
  isEmpty() {
    return this.length === 0;
  }
  size() {
    return this.length;
  }
  getHead() {
    return this.head.element;
  }
  getTail() {
    return this.tail.element;
  }
  insert(position, element) {
    // 判断是否越界
    if (position < 0 || position > this.length) return false;
    // 创建要插入的节点
    let newNode = new Node(element);
    if (position === 0) {
      // 在第一个位置插入
      if (this.head === null) {
        this.head = newNode;
        this.tail = newNode;
      } else {
        this.head.prev = newNode;
        newNode.next = this.head;
        this.head = newNode;
      }
    } else if (position === this.length) {
      // 插入到最后的情况
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    } else {
      // 在中间位置插入数据
      let index = 0;
      let current = this.head;
      let previous = null;
      // 查找正确的位置
      while (index++ < position) {
        // 重新设置previous和current的值
        previous = current;
        current = current.next;
      }
      // 交换节点的指向顺序
      newNode.next = current;
      newNode.prev = previous;
      current.prev = newNode;
      previous.next = newNode;
    }
    this.length++;
    return true;
  }
  removeAt(position) {
    // 1.判断越界的问题
    if (position < 0 || position >= this.length) return null;
    // 2.判断移除的位置
    let current = this.head;
    if (position === 0) {
      if (this.length === 1) {
        this.head = null;
        this.tail = null;
      } else {
        // 移除头，并且长度不是1
        this.head = this.head.next;
        this.head.prev = null;
      }
    } else if (position === this.length - 1) {
      current = this.tail;
      this.tail = this.tail.prev;
      this.tail.next = null;
    } else {
      let index = 0;
      let previous = null;
      while (index++ < position) {
        previous = current;
        current = current.next;
      }

      previous.next = current.next;
      current.next.prev = previous;
    }
    this.length--;
    return current.element;
  }
  indexOf(element) {
    // 1.定义变量保存信息
    let current = this.head;
    let index = 0;
    // 查找出正确的位置
    while (current) {
      // 如果节点element和element相同，则返回出index
      if (current.element === element) {
        return index;
      }
      // 不相同接着向下查找
      index++;
      current = current.next;
    }
    return -1;
  }
  remove(element) {
    let index = this.indexOf(element);
    return this.removeAt(index);
  }
}
let list = new DoublyLinkedList();

// 2.追加元素
list.append("abc");
list.append("cba");
list.append("nba");
list.append("mba");
list.insert(1, "100");
list.insert(3, "300");
console.log(list.forwardString());
list.removeAt(2);
console.log(list.reverseString());
console.log(list.getTail());
